package com.gaogzhen.datastructure.linear;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Consumer;

/**
 * @author Administrator
 * @version 1.0
 * @description 单向循环链表
 * @date 2022-10-24 21:09
 */
public class CircularList<E> {
    /**
     * 节点类
     * @param <E>
     */
    private static class Node<E> {
        E item;
        Node<E> next;
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    private int size;
    private Node<E> first;
    private Node<E> last;

    public CircularList() {}

    /**
     * 添加元素e
     * @param e     目标元素
     * @return      添加是否成功
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * 插入链表末尾
     * @param e     目标元素
     */
    private void linkLast(E e) {
        Node<E> l = last;
        Node<E> newNode = new Node<>(e, null);
        last = newNode;
        if (l == null) {
            first = newNode;
            newNode.next = newNode;
        } else {
            newNode.next = first;
            l.next = newNode;
        }
        size++;
    }

    /**
     * 插入链表头
     * @param e     目标元素
     */
    private void linkFirst(E e) {
        Node<E> f = first;
        Node<E> newNode = new Node<>(e, null);
        first = newNode;
        if (f == null) {
            last = newNode;
            newNode.next=newNode;
        } else {
            last.next = newNode;
            newNode.next = f;
        }
        size++;
    }

    /**
     * 指定索引位置插入元素
     * @param index     索引
     * @param e         目标元素
     */
    public void add(int index,E e) {
        checkPositionIndex(index);
        if (index == size) {
            linkLast(e);
        } else if (index == 0) {
            linkFirst(e);
        } else {
            linkAfter(e, nodeBefore(index));
        }
    }

    private Node<E> nodeBefore(int index) {
        Node<E> x = first;
        for (int i = 0; i < index - 1; i++) {
            x = x.next;
        }
        return x;
    }

    private void linkAfter(E e, Node<E> before) {
//        assert before != null;
        before.next = new Node<>(e, before.next);
    }

    private Node<E> node(int index) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    /**
     * 检查位置索引是否合法
     * @param index     目标索引
     */
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }


    /**
     * 检查是否合法的索引
     * @param index     目标索引
     * @return          是否合法
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    /**
     * 情况链表
     */
    public void clear() {
        if (first == null) {
            return;
        }
        last.next = null;
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x = next;
        }
        first = last = null;
        size = 0;
    }

    /**
     * 获取指定索引处的元素
     * @param index     目标索引
     * @return          指定索引处的元素
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    /**
     * 返回元素在链表中的索引位置
     * @param o     目标元素
     * @return      目标元素在链表中的索引
     */
    public int indexOf(Object o) {
        if (size == 0) {
            return -1;
        }
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != last; x = x.next) {
                if (x.item == null) {
                    return index;
                }
                index++;
            }
            if (last.item == null) {
                return size - 1;
            }
        } else {
            for (Node<E> x = first; x != last; x = x.next) {
                if (o.equals(x.item)) {
                    return index;
                }
                index++;
            }
            if (o.equals(last.item)) {
                return size - 1;
            }
        }

        return -1;
    }

    /**
     * 移除链表指定索引位置的元素
     * @param index     目标索引
     * @return          目标索引位置的元素值
     */
    public E remove(int index) {
        checkElementIndex(index);
        if (index == 0) {
            return unlinkFirst();
        }
        return unlink(nodeBefore(index));
    }

    private E unlinkFirst() {
        // assert first != null;
        Node<E> f = this.first;
        if (size == 1) {
            first = last = null;
        } else {
            last.next = first = first.next;
        }
        E item = f.item;
        f.item = null;
        f.next = null;
        size--;
        return item;
    }

    private E unlinkLast() {
        // assert first != null;
        Node<E> l = last;
        if (size == 1) {
            first = last = null;
        } else {
            Node<E> prev = nodeBefore(size - 2);
            prev.next = first;
            last = prev;
        }
        E item = l.item;
        l.item = null;
        l.next = null;
        size--;
        return item;
    }

    private E unlink(Node<E> prev) {
        // assert prev != null && prev.next != null;
        Node<E> t = prev.next;
        Node<E> next = t.next;
        E item = t.item;
        t.item = null;
        t.next = null;
        prev.next = next;
        if (next == first) {
            last = prev;
        }
        size--;
        return item;
    }

    /**
     * 移除链表中的指定元素
     * @param o     目标元素
     * @return      是否移除成功
     */
    public boolean remove(Object o) {
        if (size == 0) {
            return false;
        }
        Node<E> prev = null;
        if (o == null) {
            for (Node<E> x = first; x != last; x = x.next, prev = x) {
                if (x.item == null) {
                    if (prev == null) {
                        unlinkFirst();
                    } else {
                        unlink(prev);
                    }
                    return true;
                }
            }
            if (last.item == null) {
                unlinkLast();
                return true;
            }
        } else {
            for (Node<E> x = first; x != last; x = x.next, prev = x) {
                if (o.equals(x.item)) {
                    if (prev == null) {
                        unlinkFirst();
                    } else {
                        unlink(prev);
                    }
                    return true;
                }
            }
            if (o.equals(last.item)) {
                unlinkLast();
                return true;
            }
        }
        return false;
    }

    /**
     * 设置指定索引位置元素的值
     * @param index     目标位置索引
     * @param e         要替换的值
     * @return          被替换的旧值
     */
    public E set(int index, E e) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = e;
        return oldVal;
    }

    /**
     * 返回链表的大小
     * @return  链表的大小
     */
    public int size() { return size; }

    /**
     * 判断链表是否为空
     * @return 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    public Iterator<E> iterator() {
        return new Itr(0);
    }

    public Iterator<E> listIterator(int index) {
        checkElementIndex(index);
        return new Itr(0);
    }

    @Override
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext()) {
                return sb.append(']').toString();
            }
            sb.append(',').append(' ');
        }
    }

    private class Itr implements Iterator<E> {

        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;

        public Itr(int index) {
            next = node(index);
            nextIndex = index;
        }

        @Override
        public boolean hasNext() {
            return nextIndex < size;
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        @Override
        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            Node<E> prev = node(nextIndex - 1);
            if (prev == null) {
                unlinkFirst();
            } else {
                unlink(prev);
            }
            lastReturned = null;
            nextIndex--;
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while ( nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
        }
    }
}

